#coding:utf8
'''
这题是一道组合题
并且要求写出所有可能的合法的括号
比如 n=3 时
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]
DFS
'''

class Solution(object):
    def generateParenthesis(self, n):
        parens=[]
        def generate(p, left, right):
            if left:
                generate(p + '(', left-1, right)
            if right > left:
                generate(p + ')', left, right-1)
            if not right:
                parens.append(p)
            return parens

        return generate('', n, n)

s = Solution()
print s.generateParenthesis(3)
